|
(詳細はmaze routing problems based on Breadth-first search. 1) Initialisation - Select start point, mark with 0 - i := 0 2) Wave expansion - REPEAT - Mark all unlabeled neighbors of points marked with i with i+1 - i := i+1 UNTIL ((target reached) or (no points can be marked)) 3) Backtrace - go to the target point REPEAT - go to next node that has a lower mark than the actual node - add this node to path UNTIL (start point reached) 4) Clearance - Block the path for future wirings - Delete all marks Of course the wave expansion marks only points in the routable area of the chip, not in the blocks or already wired parts, and to minimize segmentation you should keep in one direction as long as possible. ==External links== *http://www.eecs.northwestern.edu/~haizhou/357/lec6.pdf 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Lee algorithm」の詳細全文を読む スポンサード リンク
|